package com.dylan.历史.领扣;

/**
 * @Auther: ankang
 * @Date: 2019/2/19 11:51
 * @Description:
 */
public class $0055跳跃游戏 {

    public static void main(String[] args) {
        System.out.println(new $0055跳跃游戏().canJump1(new int[]{2, 5, 0, 0}));
        System.out.println(new $0055跳跃游戏().canJump1(new int[]{3, 2 , 1, 0, 4}));
    }

    public boolean canJump1(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return true;
        }
        int maxIdx = nums[0];
        if (maxIdx >= n - 1) {
            return true;
        }
        int tempIdx;
        for (int i = 1; i < n; i++) {
            if (maxIdx < i) {
                break;
            }
            tempIdx = i + nums[i];
            if (tempIdx >= n - 1) {
                return true;
            } else if (tempIdx > maxIdx) {
                maxIdx = tempIdx;
            }
        }
        return false;
    }

    public boolean canJump(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return true;
        }
        int[] jump = new int[n];
        jump[0] = 1;
        canJumpDo(nums, jump, n, 0);
        return jump[n-1] == 1;
    }

    private void canJumpDo(int[] nums, int[] jump, int n, int idx) {
        if (jump[n-1] == 1) {
            return;
        }
        if (idx >= n) {
            return;
        }
        if (jump[idx] == 1) {
            for (int i = 1; i <= nums[idx]; i++) {
                if (idx + i < n) {
                    jump[idx + i] = 1;
                }
            }
        }
        canJumpDo(nums, jump, n, idx + 1);
    }
}
